1801D - The way home - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define fu(i, a, b) for(ll i = a; i < b; i++)
#define fd(i, a, b) for(ll i = a - 1; i >= b; i--)
#define x first
#define y second
#define pl pair<ll, ll>
#define siz(x) (ll)x.size()
#define nl '\n'
#define bit(i, k) (i & (1 << k))

const ll inf = 1e18;
const ll mod = 1e9+7;
const ll def = 1e6+1;    

template<class T> bool maxi(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}

template<class T> bool mini(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}

class comp{
public:
    bool operator() (pair<pl, pl> p1, pair<pl, pl> p2){
        if (p1.x.x != p2.x.x)
            return p1.x.x > p2.x.x;
        else
            return p1.x.y < p2.x.y;
    }
};

bool comp1(pl p1, pl p2){
    if (p1.x != p2.x)
        return p1.x < p2.x;
    else
        return p1.y > p2.y;
}

void solve(){
    ll n, m, p;
    cin >> n >> m >> p;

    ll c[n], d[n], e[n];
    fu(i, 0, n){
        cin >> c[i];
        d[i] = c[i];
    }

    vector<pl> edg[n];
    sort(d, d + n);

    fu(i, 0, n)
        e[i] = lower_bound(d, d + n, c[i]) - d;
    
    fu(i, 0, m){
        ll u, v, w;
        cin >> u >> v >> w;

        u--; v--;
        edg[u].push_back({v, w});
    }

    pl dp[n][n];
    fu(i, 0, n) 
        fu(j, 0, n)
            dp[i][j] = {inf, inf};

    dp[0][e[0]] = {0, p};
    priority_queue<pair<pl, pl>, vector<pair<pl, pl>>, comp> q;

    q.push({{0, p}, {0, e[0]}});
    while (q.size() > 0){
        ll u = q.top().y.x, i = q.top().y.y;
        ll cost = q.top().x.x, remain = q.top().x.y;

        q.pop();
        if (comp1(dp[u][i], {cost, remain}))
            continue;
        
        for (pl it : edg[u]){
            ll v = it.x, w = it.y;
            ll diff = max(w - remain, 0ll);
            ll newcost = diff / d[i];

            if ((diff % d[i]) > 0)
                newcost++;
            ll newremain = (remain + newcost * d[i]) - w;

            newcost += cost;
            ll o = max(i, e[v]);
            if (comp1({newcost, newremain}, dp[v][o])){
                q.push({{newcost, newremain}, {v, o}});
                dp[v][o] = {newcost, newremain};
            }
        }
    }

    ll res = inf;
    fu(i, 0, n)
        mini(res, dp[n - 1][i].x);

    if (res == inf)
        cout << -1 << nl;
    else
        cout << res << nl;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    ll t;
    cin >> t;

    while (t--) 
        solve();

    return 0;   
}